package algorithm.bean;

import java.util.*;

/**
 * 蚂蚁类（模拟蚂蚁行为）
 * @author letere
 * @since  2020-12-24 19:18
 */
public class Ant {
    /**
     * 信息素因子权重
     */
    private static final double ALPHA = 1.0;
    /**
     * 路线距离权重
     */
    private static final double BETA = 2.0;

    /**
     * 信息素矩阵
     */
    private final double[][] pheromoneMatrix;
    /**
     * 距离矩阵
     */
    private final int[][] distanceMatrix;

    /**
     * 当前城市：记录蚂蚁当前所在城市的ID
     */
    private Integer currentCity;
    /**
     * 城市：记录需要行走的城市ID
     */
    private final List<Integer> cities;
    /**
     * 路线：记录蚂蚁行走的路线
     */
    private final List<Integer> route;

    public Ant(double[][] pheromoneMatrix, int[][] distanceMatrix) {
        this.pheromoneMatrix = pheromoneMatrix;
        this.distanceMatrix = distanceMatrix;
        // 初始化城市集合，数字0,1,2,3...标识
        this.cities = new LinkedList<>();
        for (int i=0; i<pheromoneMatrix.length; i++) {
            cities.add(i);
        }
        // 初始化路线集合(需要形成闭环，添加回最初的城市，所以额外+1)
        this.route = new ArrayList<>(pheromoneMatrix.length + 1);
        // 选择初始城市
        Random random = new Random();
        Integer cityId = random.nextInt(cities.size());
        addRoute(cityId);
    }

    /**
     * 蚂蚁开始旅行
     */
    public void run() {
        // 循环选择下一个城市
        while (cities.size() > 0) {
            goNextCity();
        }
        // 补上最开始选择的初始城市，形成闭环
        addRoute(route.get(0));
    }

    /**
     * 前往下一个城市
     */
    private void goNextCity() {
        if(cities.size() == 1) {
            addRoute(cities.get(0));
            return;
        }
        // 计算剩余城市选择概率(通过公式)
        Map<Integer, Double> cityRateMap = new HashMap<>(16);
        double rate;
        double totalRate = 0.0;
        for (Integer city : cities) {
            rate = Math.pow(pheromoneMatrix[currentCity][city], ALPHA) * Math.pow(1.0 / distanceMatrix[currentCity][city], BETA);
            cityRateMap.put(city, rate);
            totalRate += rate;
        }
        // 通过'轮盘赌'选择下一个城市
        double randomRate = Math.random();
        double rateSum = 0.0;
        for(Map.Entry<Integer, Double> entry : cityRateMap.entrySet()) {
            rateSum += entry.getValue() / totalRate;
            if(rateSum >= randomRate) {
                addRoute(entry.getKey());
                break;
            }
        }
    }

    /**
     * 添加路线
     * @param cityId 城市id
     */
    private void addRoute(Integer cityId) {
        route.add(cityId);
        currentCity = cityId;
        cities.remove(cityId);
    }

    /**
     * 获取路线
     * @return 蚂蚁行走路线集合
     */
    public List<Integer> getRoute() {
        return route;
    }

    /**
     * 计算路线总距离
     * @return 路线总距离
     */
    public Integer getRouteLength() {
        int length = 0;
        for(int i=0; i<route.size()-1; i++) {
            length += distanceMatrix[route.get(i)][route.get(i+1)];
        }
        return length;
    }
}
